Decode Ways

Q: https://leetcode.com/problems/decode-ways/description/

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int numDecodings(String s) {
        return helper(s, 0);
    }

    private int helper(String str, int index) {
        if (memo.containsKey(index)) {
            return memo.get(index);
        }
        if (index == str.length()) {
            return 1;
        }
        if (str.charAt(index) == '0') {
            return 0;
        }
        if (index == str.length() - 1) {
            return 1;
        }
        int ans = helper(str, index + 1);
        if (Integer.parseInt(str.substring(index, index + 2)) <= 26) {
             ans += helper(str, index + 2);
         }
        memo.put(index, ans);
        return ans;
    }
}

Swap Nodes in Pairs

Q: https://leetcode.com/problems/swap-nodes-in-pairs/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp = new ListNode();
        ListNode next = head.next;
        temp.next = next;
        head.next = swapPairs(next.next);
        next.next = head;
        return temp.next;
    }
}

First Missing Positive

Q: https://leetcode.com/problems/first-missing-positive/description/

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean findOne = false;
        for (int i = 0; i < n;i++) {
            if (nums[i] == 1) {
                findOne = true;
            }
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = 1;
            }
        }
        if (findOne == false) {
            return 1;
        }
        for (int num : nums) {
            int index = Math.abs(num);
            if (index == n) {
                nums[0] =  -Math.abs(nums[0]);
            } else {
                nums[index] = - Math.abs(nums[index]);
            }
        }
        for (int i = 1; i < n;i++) {
            if (nums[i] > 0) {
                return i;
            }
        }
        if (nums[0] > 0) {
            return n;
        }
        return n + 1;
    }
}

4Sum II

Q: https://leetcode.com/problems/4sum-ii/description/

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> countBySum = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                int sum = num1 + num2;
                countBySum.put(sum, countBySum.getOrDefault(sum, 0) + 1);
            }
        }
        int count = 0;
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                int sum = num3 + num4;
                count += countBySum.getOrDefault(-sum, 0);
            }
        }
        return count;
    }
}

Sqrt(x)

Q: https://leetcode.com/problems/sqrtx/description/

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }
        int left = 2;
        int right = x / 2;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            long num = (long)mid * mid;
            if (num > x) {
                right = mid - 1;
            }
            else if (num < x) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return Math.min(left, right);
    }
}